This invention relates to pipeline sorting of ordered streams of data items, which may be used to sort timestamps of data items within a packet switching system, and to providing jitter buffers at various switching stages of a packet switch.
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ systems having greater speed and capacity (i.e., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Packet technology typically allows a plurality of information types to be transmitted over the same transmission lines and using the same packet switching systems and devices.
As used herein, the term xe2x80x9cpacketxe2x80x9d is used to indicate generically addressable information packets of all types, including fixed length cells and variable length packets. Moreover, the information contained in such packets could represent one or more of an unlimited type of information, including voice, data, video, and audio information. Furthermore, the term xe2x80x9csystemxe2x80x9d is used generically herein to describe one or more systems, networks, computer or communication devices or mechanisms, or combinations thereof.
Consumers and designers of these systems typically desire increased performance at a reasonable price. A commonly used technique for helping to achieve this goal is for these systems to provide multiple paths between a source and a destination. Packets of information are then dynamically routed and distributed among these multiple paths. It is typically more cost-effective to provide multiple slower rate links or switching paths, than to provide a single higher rate path. Such designs also achieve other desired performance characteristics.
An artifact of using dynamic routing is the need to resequence each of the streams of packets dynamically routed through a packet switch to an output port respectively back into their original order. Moreover, improved methods and systems for sequencing and resequencing of data items in this and other communications and computing environments are needed. Some packet switches manipulate an actual packet of information (including payload), while other packet switches manipulate a data item representing a packet rather than the whole packet for certain operations. The invention covers these and other variants of packet switch implementations.
Merge sorting, illustrated in FIG. 1, is a known technique for producing a single sorted list from multiple ordered lists whose values are known a priori. For example, two lists 920 and 922 of known elements sorted in ascending order can be combined into a single sorted list 924 by repeatedly taking the smaller value from the top of lists 920 and 922 and appending the smaller value to the end of list 924. This example can be extended to a set of known n values, which can be sorted by first dividing the set into n lists containing a single value each, then combining pairs of lists to produce n/2 lists with two values each. Pairs of these lists are then merged, producing n/4 lists with four values each. Continuing in this fashion eventually yields a single sorted list containing the original values, but in sorted order, as shown in FIG. 1. Merge sorting can also be implemented using three-way merging (that is, merging three sorted lists into a single sorted list in one step) for three lists of known items, rather than by using two-way merging. More generally, d-way merging is possible for any integer d greater than 1 for sorting d sorted lists of known values.
However, known sorting techniques are not candidates for resequencing streams of packets in a packet switching environment. In such a dynamic environment, lists of known values are not available. In dynamic resequencing systems, a complete set of packets to be resequenced is routinely not available at the time resequencing decisions must be made. Furthermore, the resequencing process is additionally complicated because the streams of packets to be resequenced can be temporarily empty.
New methods, apparatus, and systems for sequencing and resequencing information in a dynamic environment are needed, including those which perform resequencing dynamically routed packets in a packet switch.
Additionally, because of congestion within a packet switch dynamically routing packets, the time required for a packet to traverse the packet switch will vary substantially, which is sometime referred to as packet xe2x80x9cburstinessxe2x80x9d within the packet switch. When packets of an ordered packet stream arrive at an output interface before previous packets of the stream, these early arriving packets must be held in buffers until the previous packets arrive. Typically, a significant number of buffers must be placed in the output interfaces of a packet switch to hold these packets. Needed are new methods, apparatus, and systems for reducing the burstiness of packet traffic within a packet switch.
A method is disclosed for producing a single ordered stream of data items. An embodiment partitions the ordered streams of data items into a plurality of groups. Then, the processes of determining a first group data item for each of the plurality of groups to produce a plurality of first group data items, and determining a first system data item from the plurality of the first group data items are repetitively performed to produce the single ordered stream of data items.